package com.yun.algorithmproblem.leetcode;

import java.util.*;

/**
 * 3138. 同位字符串连接的最小长度
 * <p>
 * 给你一个字符串 s ，它由某个字符串 t 和若干 t  的 同位字符串 连接而成。
 * <p>
 * 请你返回字符串 t 的 最小 可能长度。
 * <p>
 * 同位字符串 指的是重新排列一个单词得到的另外一个字符串，原来字符串中的每个字符在新字符串中都恰好只使用一次。
 */
public class Leetcode3138 {

    public static void main(String[] args) {
        Leetcode3138 obj = new Leetcode3138();
        String s = "aabbabab";
        int cnt = obj.minAnagramLength(s);
        System.out.println(cnt);
    }

    public int minAnagramLength(String s) {
        char[] sCharArray = s.toCharArray();
        int length = s.length();
        List<Integer> factors = new ArrayList<>();
        // 遍历从 1 到 sqrt(n) 的所有数字
        for (int i = 1; i <= Math.sqrt(length); i++) {
            if (length % i == 0) {
                factors.add(i); // i 是因数
                if (i != length / i) { // 防止重复添加平方根
                    factors.add(length / i); // n / i 也是因数
                }
            }
        }
        Collections.sort(factors,Collections.reverseOrder());
        for (Integer i : factors) {
            int[] count = new int[26];
            int copies = length / i;
            for (int j = 0; j < copies; j++) {
                count[sCharArray[j] - 97]++;
            }
            boolean isCnt = true;
            outer:
            for (int j = copies; j < length; j += copies) {
                int[] count1 = new int[26];
                for (int k = j; k < j + copies && k < length; k++) {
                    count1[sCharArray[k] - 97]++;
                }
                for (int k = 0; k < 26; k++) {
                    if (count[k] != count1[k]) {
                        isCnt = false;
                        break outer;
                    }
                }
            }
            if (isCnt) {
                return copies;
            }
        }
        return length;
    }
}
